package com.linchong.dynamicprogramming.medium;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-18 17:55
 * @Description: CountBits$338-比特位计数-https://leetcode-cn.com/problems/counting-bits/
 */
public class CountBits {

	/**
	 *给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
	 *
	 * 示例 1:
	 *
	 * 输入: 2
	 * 输出: [0,1,1]
	 * 示例 2:
	 *
	 * 输入: 5
	 * 输出: [0,1,1,2,1,2]
	 * 进阶:
	 *
	 * 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
	 * 要求算法的空间复杂度为O(n)。
	 * 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。
	 *
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/counting-bits
	 *
	 * 【分析】
	 *
	 *  对于每一个数0<=i<=N，直接求i的二进制表示中有多少1
	 *      二进制表示算法：
	 *          第一步：i mod 2是最低位的bit
	 *          第二步：i <- floor(i/2),如果i=0,结束，否则会回到第一步
	 *
	 *      时间复杂度：O（NlogN）
	 *          2个数有一位二进制 0 1
	 *          2个数有2位二进制：2,3
	 *          4个数有3位二进制 4 5 6 7
	 *          8个数有4位二进制 8 9 10 11 12 13 14 15
	 *          ...
	 *          大约有N/2个数有log2N为二进制
	 *
	 * step 1:确定状态：
	 * 观察一个数的二进制位：
	 * 	    （170）10=（10101010）2
	 * 最后一步： 观察这个数最后一个二进制位（最低位），去掉它，看剩下1的个数
	 *
	 * 	    （170）10=（10101010）2
	 * 	    （85）10=（1010101）2
	 *
	 * 	    85二进制中有4个1
	 * 	    170二进制里面有4个1
	 *
	 * 子问题：
	 *      要求N的二进制中有多少1
	 *      在N的二进制去掉最后一位N mod 2,设新的数是Y=(X>>1)(右移一位)
	 *      子问题：  要知道Y的二进制表示中有多少1
	 *
	 *  状态：设f[i]表示i的二进制表示中有多少个1
	 *
	 * 注意：和位相关的动态规划一般用值作为状态
	 * step 2:转移方程：
	 *      f[i] = f[i>>1]+(i mod 2)
	 *   i的二进制中有多少个1    i的二进制表示中去掉最后一位，剩下的1的个数 i的二进制表示中最后一位
	 *
	 * step 3:初始条件 f[0]=0
	 *
	 * step 4:计算顺序：f[0],f[1],f[2],f[3],...,f[n]
	 *
	 * 时间复杂度：O(N)，空间复杂度：O(N)
	 *
	 *
	 */

	public int[] countBits(int num) {

		// 0 - num
		int [] f = new int[num+1];
		f[0] = 0;
		for (int i = 0; i <= num ; i++) {
			// 如果这里是求有多少0的话，i%2->(i+1)%2,有余数，说明末尾为0
			f[i] = f[i>>1]+(i % 2);
		}
		return f;
	}
	public static void main(String[] args) {
		int num = 5;
		CountBits instance = new CountBits();
		instance.countBits(num);
	}
}









